# 旋转数组： https://leetcode-cn.com/problems/rotate-array/

# 第一种方法，我自己写出来的。 使用空间 k 大小的数组
class Solution:
    def rotate(self, nums, k):
        """
        Do not return anything, modify nums in-place instead.
        空间复杂度O(K)， 使用一个 k长度的数组。 先将 n-k 到 k 的元素保存起来， 
        0到n-k的字符前移k长度， 再 将 保存的元素依次插入nums前面空出的位置。
        """
        n = len(nums)
        k = k % n

        temp = list()
        for i in range(n-k, n):
            temp.append(nums[i])

        for i in range(n-k-1, -1, -1):
            nums[i+k] = nums[i]
        
        for i in range(k):
            nums[i] = temp[i]
        
        return nums


# 解法二， 环形替换。 因为会发现，按照 k 间隔相移动，会出现一个环。 需要替换所有的环
''' 
再介绍一下 do while 循环再Python中如何进行替换。 因为观察下面代码可以发现，
while start != cur and i < 7: 和初始条件是冲突的，所以需要先执行一次再进行判断！ 
这里使用 while True 进行替换。
'''
# class Solution:
#     def rotate(self, nums: List[int], k: int) -> None:
#         """
#         Do not return anything, modify nums in-place instead.

#         环状替换
#         """
#         n = len(nums)
#         k = k % n
        
#         # start: 开始元素。 nt：下一个元素(当前元素要放置的位置)。cur：当前处理元素
#         start, nt, cur = 0, 0, -1
#         # i 用来计数
#         i = 0
#         while i < n:
#             # temporary, 临时的
#             temp = nums[start]
#             while start != cur and i < 7:
#                 nt = (cur + k) % n
#                 # temp = nums[nt]
#                 # nums[nt] = nums[cur]  下面一句代替这两句
#                 temp, nums[nt] = nums[nt], temp
#                 cur = nt
#                 i += 1
            
#             start += 1
#             cur = start
            
#         return nums



# 解法二
class Solution:
    def rotate(self, nums, k):
        """
        Do not return anything, modify nums in-place instead.

        环状替换
        """
        n = len(nums)
        k = k % n
        
        # start: 开始元素。 nt：下一个元素(当前元素要放置的位置)。cur：当前处理元素
        start, nt, cur = 0, 0, 0
        # i 用来计数
        i = 0
        while i < n:
            # temporary, 临时的
            temp = nums[start]
            while True:  # while True 相当于 其他语言中的do while 语句
                nt = (cur + k) % n 
                # temp = nums[nt]
                # nums[nt] = nums[cur]  下面一句代替这两句
                temp, nums[nt] = nums[nt], temp
                cur = nt
                i += 1
                if start == cur:
                    break

            start += 1
            cur = start
            
        return nums



        